package leetcode_81_100;

public class isScramble_87 {
    /**
     * 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
     * 扰乱字符串定义参考leetcode
     * 如果是，返回 true ；否则，返回 false 。
     * @param s1 s1 和 s2 由小写英文字母组成
     * @param s2 s1.length == s2.length
     * @return
     */
    public boolean isScramble(String s1, String s2) {
        /**
         * leetcode" --> "gr/eat"
         * "lee/t  /  co/de" --> "t/lee  /  co/de"
         * 想不出来解法，参考没有注释的高级递归解法
         * 看了一个下午，才彻底理解
         * 1ms
         */
        char[] chars_s1 = s1.toCharArray(), chars_s2 = s2.toCharArray();
        return recursion(chars_s1, 0, chars_s2, 0, chars_s1.length, Forward.all);
    }
    enum Forward {
        left, right, all
        //left     这部分字符串内部没有左右互换
        //right  这部分字符串内部左右互换
        //all       未知，两种情况都需要判断
    }

    /**
     * @param chars1 字符串s1
     * @param index1 s1当前进行匹配的起始位置
     * @param chars2 字符串s2
     * @param index2 s2当前进行匹配的起始位置
     * @param length 需要判断的长度
     * @param forward 当前字符串是否发生左右互换
     * @return
     */
    private boolean recursion (char[] chars1, int index1, char[] chars2, int index2, int length, Forward forward) {
        if (length == 0) return true;  // 如果长度为0，则返回true
        if (length == 1) return chars1[index1] == chars2[index2];  // 如果长度为1，则比较两个字符是否相等

        int[] map1 = new int[26], map2 = new int[26];
        int count1 = 0,//需要判定的字符数量
                count2 = 0,
                end2 = index2 + length - 1; //当前判断的字符串的结尾下标
        for (int i = 0; i < length - 1; i++) {
            if (forward != Forward.right) {  //未发生左右互换时，则尝试以当前位置为分界点进行分割判断
                if (++map1[chars1[index1 + i] - 'a'] <= 0) //map1中的s1的对应字符数量加1
                    count1--;      //数量增加之后还是<= 0，说明它匹配了一个s2的字符
                else count1++; //否则增加一个需要匹配的字符
                if (--map1[chars2[index2 + i] - 'a'] >= 0)   //map1中的s2的对应字符数量减1
                    count1--;
                else count1++;
                //如果count1==0，说明 index1 ~  index1+ i 的字符可以匹配到 index2 ~  index2+ i ，并且通过递归判定这一部分的内部也匹配成功
                //这里赋值 right，是因为多对多的匹配成功（此时必然发生了左右互换）和一对一的匹配成功（两种判定方法都可以使用），都可以使用发生左右互换时的判定方法
                if (count1 == 0 && recursion(chars1, index1, chars2, index2, i + 1, Forward.right)) {
                    //如果内部匹配成功，判断另一部分
                    if (recursion(chars1, index1 + i + 1, chars2, index2 + i + 1, length - i - 1, Forward.all)) {
                        return true;
                    }
                }
            }
            if (forward != Forward.left) {  //发生左右互换时，则尝试以当前位置为分界点进行分割判断
                if (++map2[chars1[index1 + i] - 'a'] <= 0)
                    count2--;
                else count2++;
                if (--map2[chars2[end2 - i] - 'a'] >= 0)
                    count2--;
                else count2++;
                //如果count2==0，说明 index1 ~  index1+ i 的字符可以匹配到  end-i ~ end   ，并且通过递归判定这一部分的内部也匹配成功
                //这里赋值 left ，是因为已经和原字符串的字符整体匹配完成，顺序必然相同，必然未左右互换时
                if (count2 == 0 && recursion(chars1, index1, chars2, end2 - i, i + 1, Forward.left)) {
                    // 把 end-i 赋值给下一次检索s2的起始坐标，达到把 i 作为分界点的目的
                    //如果内部匹配成功，判断另一部分
                    return recursion(chars1, index1 + i + 1, chars2, index2, length - i - 1, Forward.all);
                }
            }
        }
        return false;

    }



    /**
     * 动态规划解法
     * 8ms
     * @param s1
     * @param s2
     * @return
     */
    public boolean isScramble2(String s1, String s2) {
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        int n = s1.length();
        int m = s2.length();
        if (n != m) {
            return false;
        }
        boolean[][][] dp = new boolean[n][n][n + 1];
        // 初始化单个字符的情况
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = chs1[i] == chs2[j];
            }
        }

        // 枚举区间长度 2～n
        for (int len = 2; len <= n; len++) {
            // 枚举 S 中的起点位置
            for (int i = 0; i <= n - len; i++) {
                // 枚举 T 中的起点位置
                for (int j = 0; j <= n - len; j++) {
                    // 枚举划分位置
                    for (int k = 1; k <= len - 1; k++) {
                        // 第一种情况：S1 -> T1, S2 -> T2
                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                        // 第二种情况：S1 -> T2, S2 -> T1
                        // S1 起点 i，T2 起点 j + 前面那段长度 len-k ，S2 起点 i + 前面长度k
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }

}
